package my.algorithm.base;

/**
 * @author: marshal
 * @date: 2021-08-18 8:36 PM
 * <p>
 * 递归定义：
 * <p>
 * <p>
 * 参考：
 * 1. https://www.zhihu.com/question/31412436/answer/683820765
 * <p>
 * 总结：
 * 写出递归需要把握的要诀就是：第一，写出递推公式；第二，找到终止条件
 */
public class RecursionTest {

    public static void main(String[] args) {
//        System.out.println(fn(5));
//        System.out.println(f1(10));
        System.out.println(f3(3));
    }

    /**
     * n!
     *
     * @param n
     * @return
     */
    private static int f1(int n) {
        if (n <= 2) {
            return n;
        }
        return n * f1(n - 1);
    }

    /**
     * 斐波那契数列
     * 斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
     *
     * @return
     */
    private static int f2(int n) {
        if (n <= 2) {
            return 1;
        }
        return f2(n - 1) + f2(n - 2);
    }

    /**
     * 小青蛙跳台阶
     * <p>
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     *
     * @param n
     * @return
     */
    private static int f3(int n) {
        if (n <= 2) return n;
        return f3(n - 1) + f3(n - 2);
    }

}
